|
In computer science, an order statistic tree is a variant of the binary search tree (or more generally, a B-tree〔(【引用サイトリンク】title=Counted B-Trees )〕) that supports two additional operations beyond insertion, lookup and deletion: * Select(''i'') — find the ''ith smallest element stored in the tree * Rank(''x'') – find the rank of element ''x'' in the tree, i.e. its index in the sorted list of elements of the tree Both operations can be performed in time in the average case; when a self-balancing tree is used as the base data structure, this bound also applies in the worst case. To turn a regular search tree into an order statistic tree, the nodes of the tree need to store one additional value, which is the size of the subtree rooted at that node (i.e., the number of nodes below it). All operations that modify the tree must adjust this information to preserve the invariant that size() = size] + 1 where size() = 0 by definition. Select can then be implemented asfunction Select(t, i) // Returns the i'th element (zero-indexed) of the elements in t r ← size else if i < r return Select(left(), i) else return Select(right(), i - (r + 1)) Rank can be implemented as function Rank(T, x) // Returns the position of x (one-indexed) in the linear sorted list of elements of the tree T r ← size r ← r + size[left[y.p]] + 1 y ← y.p return r Order-statistic trees can be further amended with bookkeeping information to maintain balance (e.g., tree height can be added to get an order statistic AVL tree, or a color bit to get a red-black order statistic tree). Alternatively, the size field can be used in conjunction with a weight-balancing scheme at no additional storage cost. Another way to implement an order statistic tree is an implicit data structure derived from the min-max heap. ==References== 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「order statistic tree」の詳細全文を読む スポンサード リンク
|